﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//4.盛水容器
// https://leetcode.cn/problems/container-with-most-water/
//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int left = 0, right = height.size() - 1, ret = 0;
//        int tmp;
//        while (left < right)
//        {
//            tmp = min(height[left], height[right]) * (right - left);
//            ret = max(ret, tmp);
//            if (height[left] < height[right])
//                left++;
//            else right--;
//        }
//        return ret;
//    }
//};
//5.三角形个数
// https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/
//给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
//class Solution {
//public:
//    int triangleNumber(vector<int>& nums) {
//        int n = nums.size();
//        if (n < 3) return 0;
//        sort(nums.begin(), nums.end());//排个序先 利用单调性
//        int count = 0;
//        for (int i = n - 1; i >= 2; i--)
//        {
//            int left = 0, right = i - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] > nums[i])
//                {
//                    count += (right - left);
//                    right--;
//                }
//                else
//                    left++;
//            }
//        }
//        return count;
//    }
//};
//6.和为s
// https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/
//购物车内的商品价格按照升序记录于数组 price。
//请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& price, int target) {
//        int n = price.size();
//        int left = 0, right = n - 1;
//        while (left < right)
//        {
//            int tmp = price[left] + price[right];
//            if (tmp > target)
//                right--;
//            else if (tmp < target)
//                left++;
//            else
//            {
//                return{ price[left],price[right] };//隐式转换
//            }
//        }
//        return { 114514,15 };
//    }
//};
//7.三数之和 https://leetcode.cn/problems/3sum/
//class Solution //优化代码
//{
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        vector<vector<int>> ret;
//        // 1. 排序
//        sort(nums.begin(), nums.end());
//        // 2. 利⽤双指针解决问题
//        int n = nums.size();
//        for (int i = 0; i < n; ) // 固定数 a
//        {
//            if (nums[i] > 0) break; // ⼩优化
//            int left = i + 1, right = n - 1, target = -nums[i];
//            while (left < right)
//            {
//                int sum = nums[left] + nums[right];
//                if (sum > target) right--;
//                else if (sum < target) left++;
//                else
//                {
//                    ret.push_back({ nums[i], nums[left], nums[right] });
//                    left++, right--;
//                    // 去重操作 left 和 right
//                    while (left < right && nums[left] == nums[left - 1]) left++;
//                    while (left < right && nums[right] == nums[right + 1]) right--;
//                }
//            }
//            // 去重 i 
//            i++;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};
//class Solution { //石山代码
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        vector<vector<int>> ret;
//        for (int i = 0; nums[i] <= 0 && i < n - 2;)
//        {
//            int left = i + 1, right = n - 1;
//            while (left < right)
//            {
//                int tmp = nums[left] + nums[right];
//                int abs = -nums[i];
//                if (tmp < abs)
//                {
//                    int tmp_left = nums[left];
//                    if (tmp_left != nums[left + 1])
//                        left++;
//                    else
//                        while (left < right && tmp_left == nums[left + 1])
//                            left++;
//                }
//                else if (tmp > abs)
//                {
//                    int tmp_right = nums[right];
//                    if (nums[right] != nums[right - 1])
//                        right--;
//                    else
//                        while (left < right && tmp_right == nums[right - 1])
//                            right--;
//                }
//                else
//                {
//                    ret.push_back({ nums[i],nums[left],nums[right] });
//                    int tmp_left = nums[left];
//                    if (tmp_left != nums[left + 1])
//                        left++;
//                    else
//                        while (left < right && tmp_left == nums[left + 1])
//                            left++;
//                    int tmp_right = nums[right];
//                    if (nums[right] != nums[right - 1])
//                        right--;
//                    else
//                        while (left < right && tmp_right == nums[right - 1])
//                            right--;
//                }
//            }
//            int tmp_i=nums[i];
//            if (tmp_i != nums[i + 1])
//                i++;
//            else
//                while (i < left && tmp_i == nums[i + 1])
//                    i++;
//        }
//        return ret;
//    }
//};

//8.四数之和 https://leetcode.cn/problems/4sum/
//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target) {
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        vector<vector<int>> ret;
//        for (int i = 0; i < n - 1;)
//        {
//            for (int j = i + 1; j < n - 2;)
//            {
//                long long int target_ = (long long int)target - nums[i] - nums[j];
//                int left = j + 1, right = n - 1;
//                while (left < right)
//                {
//                    int sum = nums[left] + nums[right];
//                    if (sum < target_)left++;
//                    else if (sum > target_)right--;
//                    else
//                    {
//                        ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
//                        left++; right--;
//                        while (left < right && nums[left] == nums[left - 1])  left++;
//                        while (left < right && nums[right] == nums[right + 1]) right--;
//                    }
//
//                }
//                j++;
//                while (j < n - 2 && nums[j] == nums[j - 1]) j++;
//            }
//            i++;
//            while (i < n - 1 && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};
int main()
{
    vector<int> d { 1,-1,-1, 0};
    auto ret=Solution().fourSum(d,4);
    return 0;
}